package lc.q151_200;

public class Q174 {

    public int calculateMinimumHP(int[][] dungeon) {
        // 换种思路动态规划，从后面往前面算
        if (dungeon.length == 0) {
            return 1;
        }
        // dp存放到每一个格子需要最少血量
        int[][] dp = new int[dungeon.length][dungeon[0].length];
        for (int i = dungeon.length - 1; i >= 0; i--) {
            for (int i1 = dungeon[i].length - 1; i1 >= 0; i1--) {
                int i2 = dungeon[i][i1];
                // 判断i2的值
                if (i==dungeon.length-1 && i1==dungeon[i].length-1) {
                    dp[i][i1] = Math.max(1, - dungeon[i][i1] + 1);
                } else if (i == dungeon.length - 1) {
                    // dp[i][i1]最低需要的是后一个最低需要减去当前的量然后与1比较
                    dp[i][i1] = Math.max(dp[i][i1+1] - dungeon[i][i1], 1);
                } else if (i1 == dungeon[i].length - 1) {
                    dp[i][i1] = Math.max(dp[i+1][i1] - dungeon[i][i1], 1);
                } else {
                    dp[i][i1] = Math.max(dp[i][i1+1] - dungeon[i][i1], 1);
                    dp[i][i1] = Math.min(Math.max(dp[i+1][i1] - dungeon[i][i1], 1), dp[i][i1]);
                }
            }
        }

        return dp[0][0];
    }


    public static void main(String[] args) {
        int[][] nums = {
                {-2,-3,3},
                {-5,-10,1},
                {10,30,-5}
        };
        Q174 q174 = new Q174();
        int i = q174.calculateMinimumHP(nums);
        System.out.println(i);
    }

}
